# rod cutting 
# import random
# N = 10
# db = {0: 0, 1: 4, 2: 9, 3: 9, 4: 12, 5: 15, 6: 18, 7: 22, 8: 23, 9: 25, 10: 37}
# mv = db
# md = {}
# for n in range(1, N+1):
#     md[n] = (0, n)
#     for x in range(int(n/2) + 1):
#         tmp = mv[x] + mv[n-x]
#         if mv[n] < tmp:
#             mv[n] = tmp
#             md[n] = (x, n-x)
# print(mv)
# print(md)

#matrix product
# import numpy as np
# N = 7
# BIG = 999999

# p=[30,35,15,5,10,20,25,1]
# x=[]
# for n in range(N-1):
#     ma = np.random.randint(low=1,high=10,size=(p[n],p[n+1]))
#     x.append(ma)
#     # print(ma)
#     # print('\n')

# m = np.ndarray((N,N), dtype=int) 
# r = np.ndarray((N,N), dtype=int)
# m.fill(BIG)
# r.fill(0)
# np.fill_diagonal(m, 0)

# for j in range(2, N):
#     for i in range(j-1, 0, -1):
#         # minProd = BIG
#         for k in range(i, j):
#             tmp = m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j]
#             if m[i, j] > tmp:
#                 m[i, j] = tmp
#                 r[i, j] = k
# print(m)
# print(r)


#optimal binary tree
# import numpy as np
# N = 6  # n=5 actually
# BIG = 999999


# p=[BIG, 0.15,0.10,0.05,0.10,0.20]
# q=[0.05,0.1,0.05,0.05,0.05,0.1]
# e = np.zeros((N+1,N))
# w = np.zeros((N+1,N))
# root = np.zeros((N,N))
# e.fill(BIG)
# w.fill(BIG)
# for i in range(1,N+1):
#     w[i, i-1] = e[i, i-1] = q[i-1]

# for i in range(1,N):
#     for j in range(i, N):
#         w[i, j] = w[i, j-1] + p[j] + q[j]
#     e[i,i] = q[i-1] + q[i] + w[i, i]

# for j in range(1, N):
#     for i in range(j, 0, -1):
#         for r in range(i, j+1):
#             tmp = e[i, r-1] + e[r+1, j] + w[i,j]
#             if tmp <= e[i,j]:
#                 e[i,j] = tmp
#                 root[i, j] = r

# print(root)

#longest common subsequence
import numpy as np

X = ['A','B','C','B','D','A','B']
Y = ['B','D','C','A','B','A']
X.insert(0, None)
Y.insert(0, None)
c = np.zeros((len(X), len(Y)))
b = np.zeros((len(X), len(Y)), dtype=list)
for i in range(1, len(X)):
    for j in range(1, len(Y)):
        if X[i] == Y[j]:
            c[i, j] = c[i-1, j-1] + 1
            b[i,j] = "ij-1"
        elif c[i, j-1] > c[i-1, j]:
            c[i, j] = c[i, j-1]
            b[i,j] = "j-1"
        else:
            c[i, j] = c[i-1, j]
            b[i,j] = "i-1"
print(c)
print(b)
i, j = len(X)-1, len(Y)-1
LCS = []
while i != 0 and j != 0:
    if b[i,j] == "ij-1":
        LCS.insert(0, X[i])
        i -= 1
        j -= 1
    elif b[i,j] == 'j-1': j -=1
    elif b[i,j] == 'i-1': i -=1
print(LCS)